#include <iostream>
#include <vector>

using namespace std;

//bool check_num(int num)
//{
//    int count = 0, tmp = num * num;
//    while (tmp)
//    {
//        count++;
//        tmp /= 10;
//    }
//
//    tmp = num * num;
//    for (int i = 0; i <= count; i++)
//    {
//        int k = pow(10, i);
//        if ((tmp / k) + (tmp % k) == num)
//        {
//            return true;
//        }
//    }
//    return false;
//}
//
//int main()
//{
//    if (check_num(36))
//    {
//        cout << "true" << endl;
//    }
//    else
//    {
//        cout << "false" << endl;
//    }
//
//	return 0;
//}


//class Solution {
//public:
//    int findSubstringInWraproundString(string s) {
//        const string base("abcdefghijklmnopqrstuvwxyz");
//
//        int base_num = base.size(), s_num = s.size();
//        vector<vector<int>> dp(base_num + 1, vector<int>(s_num + 1));
//
//        for (int i = 1; i <= base_num; i++)
//        {
//            for (int j = 1; j <= s_num; j++)
//            {
//                if (s[j - 1] == base[i - 1])
//                    dp[i][j] = dp[i - 1][j - 1] + 1;
//            }
//        }
//
//        return dp[base_num][s_num];
//    }
//};
//
//int main()
//{
//    Solution().findSubstringInWraproundString("a");
//
//    return 0;
//}


class Solution {
public:
    int findSubstringInWraproundString(string s) {
        vector<int> dp(26);
        int k = 0;
        for (int i = 0; i < s.size(); i++)
        {
            if (i && (s[i] - s[i - 1] + 26) % 26 == 1)
            {
                k++;
            }
            else
            {
                k = 1;
            }

            dp[s[i] - 'a'] = max(dp[s[i] - 'a'], k);
        }

        int sum = 0;
        for (int i = 0; i < 26; i++)
        {
            sum += dp[i];
        }
        return sum;
    }
};

//////////////////////////////////////////

class Solution1 {
    vector<vector<int>> ans;
    vector<int> path;
    bool check[7];
public:
    vector<vector<int>> permute(vector<int>& nums) {
        dfs(nums);
        return ans;
    }

    void dfs(vector<int>& nums)
    {
        if (path.size() == nums.size())
        {
            ans.push_back(path);
            return;
        }

        for (int i = 0; i < nums.size(); i++)
        {
            if (check[i] == false)
            {
                path.push_back(nums[i]);
                check[i] = true;
                dfs(nums);
                path.pop_back();
                check[i] = false;
            }
        }
    }
};


////////////////////////////////
#include <string>
int ans = 0;

class Solution {
    int ans = 0;
public:
    int punishmentNumber(int n) {
        int sum = 0;
        for (int i = 1; i <= n; i++)
        {
            ans = 0;
            string str = to_string(i * i);
            if (dfs(str, 0, i))
            {
                sum += i * i;
            }
        }

        return sum;
    }

    bool dfs(const string& str, int pos, int target)
    {
        if (pos == str.size())
        {
            if (ans == target)
                return true;
            else
                return false;
        }

        int sum = 0;
        for (int i = pos; i < str.size(); i++)
        {
            sum = sum * 10 + str[i] - '0';
            ans += sum;
            if (dfs(str, i + 1, target))
            {
                return true;
            }
            ans -= sum;
        }

        return false;
    }
};

//int main()
//{
//    int sum = 0;
//    string str = to_string(36*36);
//    if (dfs(str, 0, 36))
//    {
//        sum += 36 * 36;
//    }
//
//    return 0;
//}